package com.datastructures2.字符串.字符串排序;

import edu.princeton.cs.algs4.Insertion;

import java.util.Comparator;

public class MSD {
	private static final int BITS_PER_BYTE =   8;
	private static final int BITS_PER_INT  =  32;   // each Java int is 32 bits
	private static final int R             = 256;   // extended ASCII alphabet size
	private static final int CUTOFF        =  0;   // cutoff to insertion sort

	// do not instantiate
	private MSD() { }

	/**
	 * Rearranges the array of extended ASCII strings in ascending order.
	 *
	 * @param a the array to be sorted
	 */
	public static void sort(String[] a) {
		int n = a.length;
		String[] aux = new String[n];
		sort(a, 0, n-1, 0, aux);
	}

	private static int charAt(String s, int d) {
		assert d >= 0 && d <= s.length();
		if (d == s.length()) return -1;
		return s.charAt(d);
	}

	private static void sort(String[] a, int lo, int hi, int d, String[] aux) {

		if (hi <= lo + CUTOFF) {
			insertion(a, lo, hi, d);
			return;
		}

		int[] count = new int[R+2];
		for (int i = lo; i <= hi; i++) {
			int c = charAt(a[i], d);
			count[c+2]++;
		}

		for (int r = 0; r < R+1; r++)
			count[r+1] += count[r];

		for (int i = lo; i <= hi; i++) {
			int c = charAt(a[i], d);
			aux[count[c+1]++] = a[i];
		}

		for (int i = lo; i <= hi; i++)
			a[i] = aux[i - lo];


		for (int r = 0; r < R; r++)
			sort(a, lo + count[r], lo + count[r+1] - 1, d+1, aux);
	}


	private static void insertion(String[] a, int lo, int hi, int d) {
		for (int i = lo; i <= hi; i++)
			for (int j = i; j > lo && less(a[j], a[j-1], d); j--)
				exch(a, j, j-1);
	}

	private static void exch(String[] a, int i, int j) {
		String temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}

		private static boolean less(String v, String w, int d) {
			for (int i = d; i < Math.min(v.length(), w.length()); i++) {
				if (v.charAt(i) < w.charAt(i)) return true;
				if (v.charAt(i) > w.charAt(i)) return false;
			}
		return v.length() < w.length();
	}

	public static void sort(int[] a) {
		int n = a.length;
		int[] aux = new int[n];
		sort(a, 0, n-1, 0, aux);
	}

	private static void sort(int[] a, int lo, int hi, int d, int[] aux) {

		if (hi <= lo + CUTOFF) {
			insertion(a, lo, hi, d);
			return;
		}

		int[] count = new int[R+1];
		int mask = R - 1;   // 0xFF;
		int shift = BITS_PER_INT - BITS_PER_BYTE*d - BITS_PER_BYTE;
		for (int i = lo; i <= hi; i++) {
			int c = (a[i] >> shift) & mask;
			count[c + 1]++;
		}

		for (int r = 0; r < R; r++)
			count[r+1] += count[r];


		// distribute
		for (int i = lo; i <= hi; i++) {
			int c = (a[i] >> shift) & mask;
			aux[count[c]++] = a[i];
		}

		// copy back
		for (int i = lo; i <= hi; i++)
			a[i] = aux[i - lo];

		// no more bits
		if (d == 4) return;

		// recursively sort for each character
		if (count[0] > 0)
			sort(a, lo, lo + count[0] - 1, d+1, aux);
		for (int r = 0; r < R; r++)
			if (count[r+1] > count[r])
				sort(a, lo + count[r], lo + count[r+1] - 1, d+1, aux);
	}

	private static void insertion(int[] a, int lo, int hi, int d) {
		for (int i = lo; i <= hi; i++)
			for (int j = i; j > lo && a[j] < a[j-1]; j--)
				exch(a, j, j-1);
	}

	// exchange a[i] and a[j]
	private static void exch(int[] a, int i, int j) {
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}


	public static void main(String[] args) {
		String[]a=new String[14];
		a[0]="she";
		a[1]="sells";
		a[2]="seashells";
		a[3]="by";
		a[4]="the";
		a[5]="sea";
		a[6]="shore";
		a[7]="the";
		a[8]="shells";
		a[9]="she";
		a[10]="sells";
		a[11]="are";
		a[12]="surely";
		a[13]="seashells";
		sort(a);
		for (String s:a){
			System.out.println(s);
		}
	}
}